Sensor networks, such as, for example, wireless sensor networks, have a wide range of applications. For example, wireless sensor networks of various technologies may be used for locating purposes, such as locating humans and/or other objects. Here, “locating” means the detection or determination of a geographical location or position. Some specialized locating or position tracking systems may be used for locating players and other objects (e.g. a ball) in sport events, such as, for example, soccer, American football, rugby, tennis, etc.
With using gathered geographic location or positioning data of players and/or a ball it is possible to derive statistical information related to the whole sports event, for example a soccer match, or related to individual teams or players. Such derived statistical information may be interesting for various reasons. On the one hand, there are various commercial interests as certain statistics and their analysis may be of particular relevance for spectators in a stadium and/or in front of a television set at home. Hence, providing certain statistics may raise more interest in sport events. On the other hand, statistical data derived from the raw positioning data may as well be used for training purposes. Here, an opponent and/or the behavior of the own team may be analyzed as well as the performance and/or health condition of individual players.
The aforementioned locating or position tracking systems may be based on various technologies. For example, location information may be determined based on the evaluation of wireless radio signals and/or magnetic fields. For this purpose transmitters and/or receivers, generally also denoted as sensors, may be placed at the individual objects (e.g. players, ball, etc.) to be located by the system. Corresponding reception and/or transmission devices may also be mounted to predetermined locations around a geographical area of interest, as e.g. a soccer field. An evaluation of signal strengths, signal propagation times, and/or signal phases, just to name a few possible technical alternatives, may then lead to sensor data streams indicative of the geographic position of individual players or objects at different time instants. Typically, a geographic location data sample is associated with a time stamp indicating at which time an object was located at which geographic position. With this combined information kinematic data, like velocity (speed), acceleration, etc. may as well be provided in addition to the location data comprising, for example, x-, y-, and z-coordinates. In the sequel of this specification the location and kinematic data delivered by the localization sensor system will also be referred to as (raw) sensor data.
In a particular example of a wireless tracking system people or objects may be equipped with tiny transmitters, which may be embedded in footwear, uniforms and balls and whose signals are picked up by a number of antennas placed around the area under observation. Receiver units process the collected signals and determine their Times of Arrival (ToA). Based on a calculation of the differences in propagation delay, each transmitter's position is then continuously determined. In addition, a computer network integrated with the wireless tracking system may analyze the position or sensor data so as to detect specific events. Operating in the 2.4 GHz band, the tracking system is globally license-free.
Based on the raw sensor data streams outputted from the locating or position tracking system so-called “events” may be detected. Thereby an event may be defined to be an instantaneous occurrence of interest at a point of time. In general, an event is associated with a change in the distribution of a related quantity that can be sensed. An event may be a primitive event, which is directly based on sensor data (kinematic data) of the tracking system, or a composite event, which is based on previously detected other events instead. That is to say, a composite event is not directly depending on raw sensor data but on other events. In ball game applications, an event may, for example, be “player X hits ball” or “player X is in possession of ball”. More complicated events may, for example, be “offside” or “foul”.
The detection of events based on underlying sensor data streams has raised increased interest in the database and distributed systems communities in the past few years. A wide range and ever growing numbers of applications nowadays, including applications as network monitoring, e-business, health-care, financial analysis, and security or the aforementioned sport-event supervision, rely on the ability to process queries over data streams that ideally take the form of time ordered series of events. Event detection denotes the fully automated processing of raw sensor data and/or events without the need of human intervention, as in many applications the vast quantity of supplied sensor data and/or events cannot be captured or processed by a human person anymore. For example, if high speed variations of players or a sports object, e.g. a ball, are to be expected, the raw sensor (locating or position tracking) data has to be determined at a sufficiently high data rate by the underlying (wireless) sensor network. Additionally, if there is a high number of players and/or objects (e.g. in soccer there are 22 players and a ball) to be traced the amount of overall geographic location and kinematic data samples per second can become prohibitively high, in particular with respect to real-time event processing requirements.
Hence, even if raw sensor and/or event data streams are analyzed and signaled fully automated, there may still be by far too many information, which is possibly not even of any interest in its entirety. In the future this problem will even get worse as more and more devices will be equipped with sensors and the possibility to provide their determined sensor data to public networks such as the Internet for (e.g., weather or temperature data determined by wireless devices like smart phones). For this reason the amount of sensor data to be processed further into certain events of interest will rapidly grow. Automated event detection may provide remedy for this by trying to aggregate the raw sensor data piece by piece and to determine more abstract and inter-dependent events, which may transfer by far more information than the raw sensor data itself. For example, beside the aforementioned soccer-related examples, such determined events could include “car X is located at crossing Y” or “traffic jam on route X”.
The problem that arises in automated event detection is the required computing power for performing event detection on possibly massively parallel sensor and/or event data streams—and all this under at least near real-time processing requirements. This problem may be solved by parallelization of event detectors, which may, for example, run on different network nodes of a computer network, which may, for example, communicate via Ethernet. Thereby an event detector automatically extracts a certain event of interest from an event or sensor data stream according to a user's event specifications. Individual event detectors may be distributed over different network nodes of a data network, wherein the different event detectors communicate using events and/or sensor data travelling through the network using different network routes and branches. Thereby, raw sensor data and/or event may be transported in data packets according to some transport protocol, like, e.g., UDP (User Datagram Protocol), TCP (Transmission Control Protocol)/IP (Internet Protocol), etc. This concept, however, causes new problems with respect to possibly unbalanced computational load among different network nodes and with respect to the synchronization of event data streams within the network. Without suitable countermeasures the computational loads among different network nodes are unbalanced and individual sensor and/or event data streams in the network are not time-synchronized to each other, which means that individual events may reach an event detector out of their original temporal order and thereby lead to false detected results.
Let us look at an exemplary soccer-scenario, wherein a plurality of parallel automatically operating event detectors is supposed to detect a pass from player A to player B. In order to detect said “pass”-event, the following preceding event sequence is required:                1. “player A is in possession of ball”,        2. “player A kicks ball”,        3. “ball leaves player A”,        4. “ball comes near player B”,        5. “player B hits ball”        
The event detection for event “player X kicks ball” may be based on the event sequence “player X near ball” and a detected acceleration peak of the ball. There are the following alternatives for setting up an automated event detector for said event “player X kicks ball”:
We may wait for individual required events—one after the other. If we have seen all the required events in the correct (temporal) order (here, any abortion criterions are disregarded for the sake of simplicity) we can say that we have seen or experienced a pass. However, for complex applications the detection of all the required events does not necessarily take place on a single network node or a CPU (Central Processing Unit) due to the parallelization of event detectors. For this reason it is not necessarily guaranteed that individual required events reach the event detector in the correct required order. This may, for example, be due to network jitter, varying and/or unbalanced CPU-load or increased network load.
Hence, we could try to buffer events and then search the buffer for the correct event pattern. But which buffer size should be used? If we say a pass has to happen within maximum 5 seconds we would have to consider events within a time period of maximum 5 seconds after the first relevant event until we have either detected the pass or until we abort. However, it is also possible that the last relevant event is computationally quite complex, what requires a small additional buffer. But what is the size of this additional buffer? And what is the buffer-size related to composite event detectors that require the “pass”-event as an input event? The event signaling delays are dependent on an entire system/network configuration, i.e., the distribution of the event detectors, as well as the network- and CPU-load. Neither the final system configuration nor the load scenario may be foreseen at the time of compilation.
Most existing event detection systems do not consider the aforementioned event signaling delay and or load balancing issues, as in a lot of cases event processing or propagation delays are not relevant. However, this is not the case particularly for highly complex real-time event detection systems, such as in financial or position tracking scenarios.
The following soccer-related example exemplifies the event delay problem on the basis of a frequently required “offside”-event detection scenario, which is schematically illustrated in FIG. 1.
Player 100 passes the ball 110 forward to his team mate 120. At the true (real) time of the pass, i.e., the time at which the ball 110 experiences an acceleration swing or peak (see FIG. 1, left), player 120 is situated in offside position by a few centimeters. Hence, the game would have to be interrupted.
However, in order to be able to distinguish between a direct pass or a dribbling of the first player 100, the pass from the first player 100 to the second player 120 may only be detected when the ball 120 really leaves the first player 100. Due to a limited data rate of the sensor data this distinguishing decision may take an additional “natural” delay of at least a few milliseconds. After this natural delay the second player 120 may, however, not be in offside-position anymore (see FIG. 1, right).
Here, just considering the temporal order of the participating automatically generated events is not enough for making the offside decision. Moreover, they have to be sorted. Not only the event computation time or network propagation delay is relevant, but also causal, real-time variations that have to be considered. The time-stamp of the detected pass event has to be reset to the past, i.e. the moment in which the ball experiences an acceleration peak.
Beside demanded general system stability it is desirable to ensure for a possibly equal computational load distribution in a distributed computing system also due to the importance of the temporal order of events for correct follow-up decisions or events.